package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;
import cn.pugle.oj.catalog.TwoProblem;

import java.util.LinkedList;

/**
 * 原计划是用ListNode带两个next指针, 一个是栈顺序, 一个是大小顺序
 * <p>
 * 根据提示发现, 此题没必要完整排序, 记录currentMin即可
 * 思想类似单调栈
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC155 implements StackProblem, TwoProblem {
    static class MinStack {
        LinkedList<Integer> originStack;
        LinkedList<Integer> curMinStack;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            originStack = new LinkedList<>();
            curMinStack = new LinkedList<>();
        }

        public void push(int x) {
            originStack.push(x);
            if (curMinStack.peek() == null || curMinStack.peek() >= x) {
                curMinStack.push(x);
            }
        }

        public void pop() {
            Integer pop = originStack.pop();
            if (pop != null && pop.equals(curMinStack.peek())) {
                curMinStack.pop();
            }
        }

        public int top() {
            return originStack.peek();
        }

        public int getMin() {
            return curMinStack.peek();
        }
    }

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(1);
        stack.push(3);
        stack.push(0);
        System.out.println(stack.getMin());
        stack.pop();
        System.out.println(stack.top());
        System.out.println(stack.getMin());
    }
}
